﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RPGProject.Data_Structures
{
    /// <summary>
    /// An implementation of a Min Heap.
    /// </summary>
    /// <typeparam name="TData"></typeparam>
    class Heap<TData> where TData : IComparable<TData>
    {
        /// <summary>
        /// The data stored.
        /// </summary>
        private TData[] data;
        /// <summary>
        /// The size of the array.
        /// </summary>
        private int size;
        /// <summary>
        /// Create a heap with the capacity specified, or default of 10.
        /// </summary>
        /// <param name="capacity"></param>
        public Heap(int capacity = 10)
        {
            this.data = new TData[capacity];
            this.size = 0;
        }
        /// <summary>
        /// Add the data to the heap, and then reheapify it.
        /// </summary>
        /// <param name="data"></param>
        public void Add(TData data)
        {
            this.data[this.size] = data;
            this.size++;
            this.Heapify(this.size - 1);
            if (this.size >= this.data.Count())
            {
                this.Resize((int)(this.size * 1.5));
            }
        }
        /// <summary>
        /// Resize the array to the specified index.
        /// </summary>
        /// <param name="x"></param>
        public void Resize(int x)
        {
            TData[] newData = new TData[x];
            for (int i = 0; i < this.data.Count(); i++)
            {
                newData[i] = this.data[i];
            }
            this.data = newData;
        }
        /// <summary>
        /// Heapify the index upwards.
        /// </summary>
        /// <param name="index"></param>
        private void Heapify(int index)
        {
            if (index == 0)
                return;
            int parent = (index - 1) / 2;
            if (this[index].CompareTo(this[parent]) < 0)
            {
                TData temp = this[index];
                this[index] = this[parent];
                this[parent] = temp;
                this.Heapify(parent);
            }
        }
        /// <summary>
        /// Heapify the index downwards.
        /// </summary>
        /// <param name="index"></param>
        private void SiftDown(int index)
        {
            if (index * 2 + 1 > this.size)
                return;
            if (index * 2 + 2 > this.size)
            {
                int min = index * 2 + 1;
                if (this[min].CompareTo(this[index]) < 0)
                {
                    TData temp = this[index];
                    this[index] = this[min];
                    this[min] = this[index];
                }
            }
            else
            {
                int left = index * 2 + 1;
                int right = index * 2 + 2;
                int min = this.Min(left, right);
                if (this[min].CompareTo(this[index]) < 0)
                {
                    TData temp = this[index];
                    this[index] = this[min];
                    this[min] = temp;
                    this.SiftDown(min);
                }
            }

        }
        /// <summary>
        /// Returns the index of the minimium object between left and right.
        /// </summary>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        private int Min(int left, int right)
        {
            if (this[left].CompareTo(this[right]) < 0)
                return left;
            else
                return right;

        }
        /// <summary>
        /// Returns the index of the data specified.
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public int IndexOf(TData data)
        {
            for (int i = 0; i < this.size; i++)
            {
                if (this[i].Equals(data))
                    return i;
            }
            return -1;
        }
        /// <summary>
        /// Remove the object specified.
        /// </summary>
        /// <param name="def"></param>
        /// <returns></returns>
        public bool Remove(TData def)
        {
            if (this.IndexOf(def) == -1)
                return false;
            this.Remove(this.IndexOf(def));
            return true;
        }
        /// <summary>
        /// Returns the minimium element and removes it.
        /// </summary>
        /// <returns></returns>
        public TData RemoveMin()
        {
            return this.Remove();
        }
        /// <summary>
        /// Removes an element from index specified.
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private TData Remove(int index = 0)
        {
            TData ret = this[index];
            this[index] = this[size - 1];
            this.size--;
            this.SiftDown(index);
            return ret;
        }
        /// <summary>
        /// Indexer to get items.
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public TData this[int index]
        {
            get { return this.data[index]; }
            set { this.data[index] = value; }
        }
        public override string ToString()
        {
            String ret = "";
            for (int i = 0; i < this.size; i++)
            {
                ret += this[i].ToString() + " ";
            }
            return ret;
        }
        /// <summary>
        /// Current Heap size.
        /// </summary>
        public int Size 
        {
            get { return this.size; }
        }
        /// <summary>
        /// Returns the first element in the Heap.
        /// </summary>
        /// <returns></returns>
        public TData GetMin()
        {
            return this.data[0];
        }

        public void Clear()
        {
            this.data = new TData[10];
            this.size = 0;
        }
    }
}
